package cxydmmszl.chapter04.t057;

import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 矩阵的最短路径
 * <li style="color: red;">Desc</li>
 * 给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。<br/><br/>
 * 输入描述：<br/>
 * 第一行输入两个整数 n 和 m，表示矩阵的大小。
 * 接下来 n 行每行 m 个整数表示矩阵。<br/><br/>
 * 输出描述：<br/>
 * 输出一个整数表示答案。
 * <li style="color: red;">Link</li> CD186
 *
 * @author habitplus
 * @since 2021-08-30 21:40
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        System.out.println(minPathSum1(arr));
//        System.out.println(minPathSum2(arr));
//        System.out.println(minPathSum3(arr));
    }

    /**
     * 原地 dp
     * 时间复杂度：O(N*M)
     * 空间复杂度：O(1)
     */
    private static int minPathSum1(int[][] arr) {
        if (arr == null || arr.length < 1 || arr[0].length < 1) return 0;
        int n = arr.length;
        int m = arr[0].length;

        for (int i = 1; i < m; i++) {
            arr[0][i] += arr[0][i - 1];
        }

        for (int i = 1; i < n; i++) {
            arr[i][0] += arr[i - 1][0];
            for (int j = 1; j < m; j++) {
                arr[i][j] += Math.min(arr[i - 1][j], arr[i][j - 1]);
            }
        }
        return arr[n - 1][m - 1];
    }

    /**
     * 以行方式 dp
     * 时间复杂度：O(N*M)
     * 空间复杂度：O(M)
     */
    private static int minPathSum2(int[][] arr) {
        if (arr == null || arr.length < 1 || arr[0].length < 1) return 0;
        int n = arr.length;
        int m = arr[0].length;

        int[] dp = new int[m];
        // 设置第一行 dp 的值
        dp[0] = arr[0][0];
        for (int i = 1; i < m; i++) {
            dp[i] = dp[i - 1] + arr[0][i];
        }

        for (int i = 1; i < n; i++) {
            dp[0] += arr[i][0]; // dp[0] 记录了 dp[0][i]
            for (int j = 1; j < m; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + arr[i][j];
            }
        }
        return dp[m - 1];
    }

    /**
     * 时间复杂度：O(N*M)
     * 空间复杂度：O(min(N, M))
     */
    private static int minPathSum3(int[][] arr) {
        if (arr == null || arr.length < 1 || arr[0].length < 1) return 0;
        int more = Math.max(arr.length, arr[0].length);
        int less = Math.min(arr.length, arr[0].length);
        boolean rowMore = more == arr.length; // 行数 >= 列数，则为 true

        int[] dp = new int[less];

        // 设置第一行 dp 的值
        dp[0] = arr[0][0];
        for (int i = 1; i < less; i++) {
            dp[i] = dp[i - 1] + (rowMore ? arr[0][i] : arr[i][0]);
        }

        for (int i = 1; i < more; i++) {
            dp[0] += rowMore ? arr[0][i] : arr[i][0]; // dp[0] 记录了 dp[0][i]
            for (int j = 1; j < less; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + (rowMore ? arr[i][j] : arr[j][i]);
            }
        }
        return dp[less - 1];
    }
}
